package Algorithm.LinkedListProblem;

/**
 * @Author cj
 * @Date 2021/11/22 19:45
 */
public class josephusKill1 {

    class Node {
        public int value;
        public Node next;

        public Node(int val) {
            this.value = val;
        }
    }

    public static Node josephusKill11(Node head, int m) {
        if (head == null || head.next == null || m < 1) {
            return head;
        }
        Node pre = head;
        // pre移到末尾
        while (pre.next != head) {
            pre = pre.next;
        }
        int count = 0;
        while (head != pre) {
            if (++count == m) {
                pre.next = head.next;
                count = 0;
            } else {
                pre = pre.next;
            }
            head = pre.next;
        }
        return head;
    }

    // 进阶解法
    public static Node josephusKill2(Node head, int m) {
        if (head == null || head.next == null || m < 1) {
            return head;
        }
        // 求节点数
        int num = 1;
        Node pre = head;
        while (pre.next != head) {
            num++;
            pre = pre.next;
        }
        // 求存活节点编号
        int index = getLive(num, m);
        while (--index > 0) {
            head = head.next;
            pre = pre.next;
        }
        pre.next = null;
        head.next = head;
        return head;
    }

    public static int getLive(int i, int m) { // 返回值是老编号
        // 终止条件
        if (i == 1) { // i代表存活节点个数
            return 1;
        }
        return (getLive(i - 1, m) + m - 1) % i + 1;
    }
}
